package com.frx.leetcode.classify.link;

/**
 * Created with IDEA
 *
 * @author: xrf
 * @Date: 2019/11/8
 * @Time: 16:11
 */
public class LinkReverse {

    public static void main(String[] args){
        ListNode l1 =  new ListNode(1);
        ListNode l2 =  new ListNode(2,l1);
        ListNode l3 =  new ListNode(3,l2);
        ListNode l4 =  new ListNode(4,l3);
        ListNode l5 =  new ListNode(5,l4);
        //printLink(l5);
        ListNode listNode1 = solution(l5);
        printLink(listNode1);
        System.out.println();
        ListNode n3 = new ListNode(4);
        ListNode n2 = new ListNode(2,n3);
        ListNode n1 = new ListNode(1,n2);
        printLink(n1);
        System.out.println();
        ListNode node = mergeLink(n1,listNode1);
        printLink(node);
    }

    public static ListNode solution(ListNode head){
        if (head == null || head.next == null){
            return head;
        }
        ListNode p1 = head;
        ListNode p2 = head.next;
        ListNode p3 = null;
        while (p2 != null){
            p3 = p2.next;
            p2.next = p1;
            p1 = p2;
            p2 = p3;
        }
        head.next = null;
        head = p1;
        return head;
    }

    public static ListNode mergeLink(ListNode l1,ListNode l2){
        ListNode result = new ListNode(1);
        ListNode r = result;
        while (l1!=null && l2!=null){
            if (l1.val < l2.val){
                r.next = new ListNode(l1.val);
                l1 = l1.next;
                r = r.next;
            } else {
                r.next = new ListNode(l2.val);
                l2 = l2.next;
                r = r.next;
            }
        }
        while (l1 != null){
            r.next = new ListNode(l1.val);
            l1 = l1.next;
            r = r.next;
        }
        while (l2 != null){
            r.next = new ListNode(l2.val);
            l2 = l2.next;
            r = r.next;
        }

        return result.next;
    }

    public static void printLink(ListNode head){
        System.out.print(head.val);
        head = head.next;
        while (head != null){
            System.out.print("->" + head.val);
            head = head.next;
        }
    }


}
class ListNode{
    int val;
    ListNode next;
    ListNode(int val){
        this.val = val;
    }
    ListNode(int val,ListNode next){
        this.val = val;
        this.next = next;
    }

}
